闲话

又是打得很惨,只出了ABC速度还慢的很,之后发现D还是很简单的一个题,E就比较麻烦了.而且比较莫名奇妙的是罚时挺高的.感觉不大应该出这种情况.

A. Yellow Cards

题目大意:有两个队伍在踢球,两个队伍各有$a_1,a_2$个人.一共下发了$n$张黄牌,当一个属于第一个队伍的队员收到了$k_1$张黄牌的时候他将直接退场,另一队类似.问最少和最多各有几个人出场.即使当两边都没有队员了比赛也会继续下去.

思路

直接模拟.对于最少的情况先直接平均分配,把每个人都分配上$k-1$个牌,最后多出几个就会出局几个.对于最多的情况,不妨让$k_1<k_2$,再贪心的一个一个出局即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int a1,a2,k1,k2;scanf("%d%d%d%d",&a1,&a2,&k1,&k2);
	int n;scanf("%d",&n);
	int __ = n;
	int minv = n / (a1 + a2);
	int res = 0;
	if(n <= a1 * (k1 - 1) + a2 * (k2 - 1))		res = 0;
	else res = n - a1 * (k1 - 1) - a2 * (k2 - 1);
	printf("%d ",res);
	res = 0;n = __;
	if(k1 > k2)	swap(k1,k2),swap(a1,a2);
	for(int i = 1;i <= a1 && n >= k1;++i)
	{
		++res;
		n -= k1;
	}
	for(int i = 1;i <= a2 && n >= k2;++i)
	{
		++res;
		n -= k2;
	}
	printf("%d",res);
    return 0;
}

B. The Number of Products

题目大意:给定一个长度为$n$的序列a,保证序列内没有0.求出整个序列里连续子序列乘积是正数和负数的情况的个数.
数据范围:
$1 \leq n \leq 2*10^5$

思路

显然对于一个元素来说,他具体是多少是不关心的,因此可以直接把正数记作$1$,负数记作$-1$.对于序列里连续子序列乘积是正数的情况,可以定义一个前缀积,问题转换成对于一个位置$i$他的前面有多少个是跟他同正负性的,对于乘积是负数的情况相反对应即可.从前往后遍历,记录两种类型的数量,再看当前的总的前缀积具体是正是负即可算出总数.注意防范爆int.
实际上只用求出一边,另一边就是总数去减,总的连续子序列的个数是$n(n+1)/2$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N],buck[2];
int main()
{
	int n;scanf("%d",&n);buck[0] = 1;
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]),a[i] = (a[i] > 0 ? 1 : -1);
	int flag = 1,sum = 1;
	ll res = 0;
	for(int i = 1;i <= n;++i)
	{
		sum *= a[i];
		res += sum > 0 ? buck[1] : buck[0];
		buck[sum > 0 ? 0 : 1] ++;
	}
	printf("%lld %lld",res,1ll*n * (n + 1) / 2 - res);
    return 0;
}

C. Swap Letters

题目大意:给定两个长度相同的字符串s和t.每次可以交换两者中任意的一对元素,问最少几次可以让两个字符串相等,只需输出数量而不需输出具体方案.字符串里只有a和b两种元素.
数据范围:
$1 \leq n \leq 2*10^5$

思路

如果上下已经相同则不需要考虑.因此可以把不同的两种情况分别统计出来.由于不同的也就那么几种,分别讨论一下就可以了.显然对于两个相同类型的不匹配元素,直接让两个位置交换一下即可以$1$的代价把两者变合法.对于两个不相同类型的需要$2$次.因此可以贪心的先对组内可以自己匹配的记录进去,直到最后不够了再两者进行组合.原问题是否有解即是否会有两种元素的和是奇数或者两种元素的数量不匹配的情况出现.稍加判断即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    string a,b;cin >> a >> b;
    vector<int> tar[2];
    int cnt1 = 0,cnt2 = 0;
    for(int i = 0;i < n;++i)
    {
    	if(a[i] != b[i])
    	{
    		if(a[i] == 'a')	tar[0].push_back(i + 1);
    		else 			tar[1].push_back(i + 1);
    	}
    	if(a[i] == 'a')	++cnt1;
    	else ++cnt2;
    	if(b[i] == 'a')	++cnt1;
    	else ++cnt2;
    }
	if(cnt1 % 2 == 1 && cnt2 % 2 == 0
	 || (tar[0].size() + tar[1].size()) % 2
	 || cnt1 % 2 == 0 && cnt2 % 2 == 1)	cout << "-1";
	else
	{
		vector<pii> op;
		while(tar[0].size() >= 2)
		{
			int x = tar[0].back();tar[0].pop_back();
			int y = tar[0].back();tar[0].pop_back();
			op.push_back({x,y});
		}
		while(tar[1].size() >= 2)
		{
			int x = tar[1].back();tar[1].pop_back();
			int y = tar[1].back();tar[1].pop_back();
			op.push_back({x,y});
		}
		if(tar[0].size())
		{
			op.push_back({tar[0].back(),tar[0].back()});
			op.push_back({tar[0].back(),tar[1].back()});
		}
		cout << op.size() << endl;
		for(auto& v : op)	cout << v.first << " " << v.second << endl;
	}    
    return 0;
}

D. Ticket Game

题目大意:两个毒瘤在一个字符串上玩游戏.定义一个字符串是牛逼的,当且仅当上面没有任何问号,并且前$n/2$个元素的和后$n/2$个元素的和是相等的.字符串上可能会有一些问号,每次两边可以选取任意一个问号并填入一个$0~9$之间的数字,最后如果字符串是牛逼的,则Bicarp胜利,反之Monocarp胜利.求谁会胜利.保证输入的$n$和问号的个数都是偶数.

思路

由于情况不是很多,先来一波讨论:
①左右两边的和相等
1'左边?的个数与右边的不同,此时只要先手不断地填$9$,则后手必然跟不上和的增大,失败.
2'左边右边数量相等,后手镜像操作必然获胜.
②左和>右和
1'左边?的个数比右边的多,此时必然是先手获胜,因为一样的可以在较大的一边不断地填9导致另一边根本跟不上而失败.
2'右边比左边多,这个时候可以把左边,也就是较少一侧的问号看错是无意义的,因为后手一定要平衡操作,这导致左右两边其实是对称的,这部分可以删掉.在右边剩下了差值个空缺,这之后先后手都只能在右边填数,只有当两者的和的$\frac{9}{2}$倍是左和-右和的时候先手才会必败,因为这个时候不管怎么填后手一定可以凑出这个9导致胜利.
③左和<右和
与上一个情况镜像.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	string s;cin >> s;
	int lc = 0,ls = 0,rc = 0,rs = 0;
	for(int i = 0;i < n / 2;++i)
	{
		if(s[i] == '?')	++lc;
		else ls += (s[i] - '0');
	}
	for(int i = n / 2;i < n;++i)
	{
		if(s[i] == '?')	++rc;
		else rs += (s[i] - '0');
	}
	if(ls == rs)
	{
		if(lc == rc)	cout << "Bicarp";
		else cout << "Monocarp";
	}
	else if(ls < rs)
	{
		if(lc <= rc)	cout << "Monocarp";		
		else if((lc - rc) / 2 * 9 == rs - ls)	cout << "Bicarp";
		else cout << "Monocarp";
	}
	else
	{
		if(lc >= rc)	cout << "Monocarp";
		else if((rc - lc) / 2 * 9 == ls - rs)	cout << "Bicarp";
		else cout << "Monocarp";
	}
    return 0;
}

E. Marbles

题目大意:有$n$个珠子,每个珠子有自己的颜色,颜色种类不超过2种.每次你可以交换两个相邻的珠子的位置,问最少要交换几次才可以使所有珠子的颜色呈段分布.
数据范围:
$2 \leq n \leq 4*10^5$

思路

假如这个题的颜色就是要线性上升,那么就是一个排序题了.而现在没有规定这个条件,实际上就可以人为的添加某个权值,把逆序对的判断拓展成权值的判断即可.对于最后的一个颜色排列来说,相当于是让先进去的权值较小,后进去的权值较大,这样才可以使整个权逆序对最少.所以当加入一个新元素进入集合的时候,他的权值比前面的都大,比后面的都小/
由于颜色很少,可以直接用二进制数表示整个集合进而状压DP.
状态:$f[i]$表示当集合是$i$的时候,最少有几个权值逆序对.
转移:对于当前的集合$i$,枚举其中每一个选进去了的数当做是最新加入这个集合的数$u$.而删除掉$u$的$i$集合记作是$j$,那么在$j$里的每个元素,都可能构成一个权逆序对,如果元素$v$构成了,那么只需要满足$l<r,a_l=u,a_r=v$即可,因为$v$是比$u$更早进入集合的,所以他的权值一定是比$u$要小的.所以这样就会构成逆序对了.那么由于颜色只有$20$种,所以可以直接先暴力统计出来,再直接$DP$即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e5+7,M = 20,_N = 1 << M;
int c[N];
ll f[_N],w[M][M],cnt[M],bound = _N;
int main()
{
	int n;scanf("%d",&n);
	
	for(int i = 0;i < n;++i)	scanf("%d",&c[i]);
	for(int i = 0;i < n;++i)
	{
		-- c[i];++ cnt[c[i]];
		for(int j = 0;j < M;++j)	w[j][c[i]] += cnt[j];
	}
	for(int i = 1,j;i < bound;++i)
	{
		f[i] = 1e18;
		for(int u = 0;u < M;++u)
		{
			if(i >> u & 1)
			{
				j = i ^ (1 << u);
				ll fres = 0;
				for(int v = 0;v < M;++v)
				{
					if(j >> v & 1)	
						fres += w[u][v];
				}
				f[i] = min(f[i],f[j] + fres);
			}
		}
	}
	printf("%lld",f[bound - 1]);
    return 0;
}